package hot100.logos31To40;

import hot100.datastruct.ListNode;

/**
 * @author logos
 * date 2025/7/13 11:22
 * @version v1.0
 * @Package hot100.logos31To40
 */
public class logos31 {

    /**
     * 31. K个一组翻转链表
     * https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode start = head;
            ListNode end = boolReverse(start, k);
            if (end == null) {
                return head;
            }
            head = end;
            reverse(start, end);
            ListNode lastEnd = start;
            while (lastEnd.next != null) {
                start = lastEnd.next;
                end = boolReverse(start, k);
                if (end == null) {
                    return head;
                }
                reverse(start, end);
                lastEnd.next = end;
                lastEnd = start;
            }
            return head;
        }

        private void reverse(ListNode start, ListNode end) {
            ListNode pre = null;
            ListNode cur = start;
            ListNode next = null;
            end = end.next;
            while (cur != end) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            start.next = end;
        }

        private ListNode boolReverse(ListNode start, int k) {
            while (start != null && --k > 0) {
                start = start.next;
            }
            return start;
        }
    }


}
